#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

bool* sieve(int n) {
    if (n <= 2) {
        bool* primes = (bool*)malloc(n * sizeof(bool));
        if (primes) {
            for (int i = 0; i < n; i++) {
                primes[i] = false;
            }
        }
        return primes;
    }
    
    bool* primes = (bool*)malloc(n * sizeof(bool));
    if (!primes) {
        fprintf(stderr, "Memory allocation failed in sieve\n");
        return NULL;
    }
    
    memset(primes, true, n * sizeof(bool));
    primes[0] = false;
    primes[1] = false;
    
    int sqrt_n = (int)sqrt((double)n) + 1;
    for (int i = 2; i < sqrt_n; i++) {
        if (primes[i]) {
            for (int j = i * i; j < n; j += i) {
                primes[j] = false;
            }
        }
    }
    
    return primes;
}

int main(int argc, char *argv[]) {
    int n = argc > 1 ? atoi(argv[1]) : 10000000;
    int runs = argc > 2 ? atoi(argv[2]) : 5;
    int print_flag = (argc > 3); // 第三个参数存在则打印
    double total_time = 0;
    
    // 预热运行（3次）
    for (int i = 0; i < 3; i++) {
        bool* primes = sieve(1000000);
        free(primes);
    }

    for (int i = 0; i < runs; i++) {
        clock_t start = clock();
        bool* primes = sieve(n);
        clock_t end = clock();
        if (print_flag) {
            for (int j = 0; j < n; j++) {
                printf("%d: %s\n", j, primes[j] ? "true" : "false");
            }
        }
        free(primes); // 释放内存
        total_time += (double)(end - start) * 1000 / CLOCKS_PER_SEC;
    }

    double avg_time = total_time / runs;
    printf("C      | %.2f ms\n", avg_time);
    return 0;
}